{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Birthday Problem: This is a classic problem that has a nonintuitive answer. Suppose there are 𝑁 students in a room."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Part a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We wish to figure out the probability that at least two of them have the same birthday (month and day)?  (Assume that each day is equally likely to be a student's birthday, that there are no sets of twins, and that there are 365 days in the year. Do not include leap years)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\"At least two\" with the same birthday could mean that exactly two students have the same birthday and all other students have birthdays different from each other and different from that one shared birthday. It could mean that two students share one birthday and two students share a different birthday and all other students have birthdays different from each other and different from either of those shared birthdays. It could mean that three students share one birthday and two students share a different birthday and all other students... this is getting difficult!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When we need to compute the probability of an event describes as \"at least\" (for example \"at least one\" or \"at least two\"), it is almost always easier to consider the complement of the event. Indeed, we have that\n",
    "\n",
    "$$P(\\text{at least two share a birthday}) = 1-P(\\text{none share a birthday})$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before solving this problem analytically, let's try to approach this via simulation using R! In the next cell, we will set $N$ to be 10 and sample birthdays for $N$ people. For simulation, considering the complement of the event will not be particularly advantageous so we will just approach the problem directly. Run the next cell to simulate 10 birthdays."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>\n",
       ".list-inline {list-style: none; margin:0; padding: 0}\n",
       ".list-inline>li {display: inline-block}\n",
       ".list-inline>li:not(:last-child)::after {content: \"\\00b7\"; padding: 0 .5ex}\n",
       "</style>\n",
       "<ol class=list-inline><li>35</li><li>56</li><li>253</li><li>303</li><li>228</li><li>33</li><li>336</li><li>245</li><li>252</li><li>132</li></ol>\n"
      ],
      "text/latex": [
       "\\begin{enumerate*}\n",
       "\\item 35\n",
       "\\item 56\n",
       "\\item 253\n",
       "\\item 303\n",
       "\\item 228\n",
       "\\item 33\n",
       "\\item 336\n",
       "\\item 245\n",
       "\\item 252\n",
       "\\item 132\n",
       "\\end{enumerate*}\n"
      ],
      "text/markdown": [
       "1. 35\n",
       "2. 56\n",
       "3. 253\n",
       "4. 303\n",
       "5. 228\n",
       "6. 33\n",
       "7. 336\n",
       "8. 245\n",
       "9. 252\n",
       "10. 132\n",
       "\n",
       "\n"
      ],
      "text/plain": [
       " [1]  35  56 253 303 228  33 336 245 252 132"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Run this cell\n",
    "N = 10\n",
    "birthdays = sample(1:365, size=N, replace = TRUE)\n",
    "birthdays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Are there any shared birthdays here? Typing `unique(birthdays)` will list all of the unique elements of the vector birthdays. If the length of this vector is shorter than the length of the original vector, we know that there is at least one duplicate."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "FALSE"
      ],
      "text/latex": [
       "FALSE"
      ],
      "text/markdown": [
       "FALSE"
      ],
      "text/plain": [
       "[1] FALSE"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Run this cell\n",
    "share = FALSE\n",
    "if(length(unique(birthdays)) < length(birthdays)) \n",
    "{\n",
    "  share = TRUE\n",
    "}\n",
    "share"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To see probability \"in action\", we will repeat our experiment many times!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "0.09"
      ],
      "text/latex": [
       "0.09"
      ],
      "text/markdown": [
       "0.09"
      ],
      "text/plain": [
       "[1] 0.09"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Number of repetitions of our simulated experiment\n",
    "numreps = 100\n",
    "\n",
    "# Inititalize a Boolean vector with all FALSE values\n",
    "share = rep(FALSE,numreps)\n",
    "\n",
    "# Start the simulation\n",
    "for(i in 1:numreps)\n",
    "{\n",
    "   birthdays = sample(1:365, size=N, replace = TRUE)\n",
    "   if(length(unique(birthdays)) < length(birthdays)) \n",
    "   {\n",
    "      share[i] = TRUE\n",
    "   }\n",
    "}\n",
    "\n",
    "\n",
    "# When R sums a vector of booleans (TRUE or FALSE) it is treating TRUE as 1 and FALSE as 0.\n",
    "# So, `sum(share)` will give the total number of \"TRUE\"s\n",
    "\n",
    "sum(share)/numreps  #proportion of runs that have duplicate birthdays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Run the cell above several times. Do you see a lot of variability in the answer? If you roll a fair six-sided die 5 times, do you really think that you will see a 3 $1/6$ of the time? To get a good estimate of that $1/6$ probability, you need to roll the die a lot! \n",
    "\n",
    "Increase \"numreps\" to 100,000 and run it several times again. (Note: R is very slow at \"looping\" so each run may take a moment. There are more efficient ways to code the simulation in R but we are using the loop as, arguably, the most straightforward method for clarity.)\n",
    "\n",
    "With each run at the higher number of reps, your estimate should be more consistent."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<hr>\n",
    "We now challenge you to work out the probability \n",
    "\n",
    "$$P(\\text{at least two share a birthday}) = 1-P(\\text{none share a birthday})$$\n",
    "\n",
    "on paper for a general $N$. If you need to look up the solution in a book or on the internet, make sure you read it carefully until you understand it. Although this is an \"ungraded lab\", skipping this challenge can hurt you as this course progresses!\n",
    "\n",
    "In the next cell, use R to work out the value of your analytical solution in the case that $N=10$. Does it match (approximately) the answer you arrived at via simulation?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Your code here\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Part b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Copy your code form the previous cell into the next cell. Alter it to determine, through trial-and-error, how  large $N$ must be so that the probability that at least two of them have the same birthday is at least 1/2? Answer this through trial and error by using R to evaluate your analytical solution for various values of $N$. \n",
    "\n",
    "(Make sure you can get the given answer!)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Your code here: The answer is 23 !!!\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Part c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For $N=1,2,\\ldots, 40$, we want to plot $N$ (the number of students) on the $x$-axis versus the probability that at least two of them have the same birthday\n",
    "on the $y$-axis. Fill in the missing code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "ename": "ERROR",
     "evalue": "Error in parse(text = x, srcfile = src): <text>:13:1: unexpected '}'\n12:    the.probability[i] = ? # Replace the question mark!\n13: }\n    ^\n",
     "output_type": "error",
     "traceback": [
      "Error in parse(text = x, srcfile = src): <text>:13:1: unexpected '}'\n12:    the.probability[i] = ? # Replace the question mark!\n13: }\n    ^\nTraceback:\n"
     ]
    }
   ],
   "source": [
    "# Your code here\n",
    "\n",
    "N = 1:40\n",
    "the.probability = rep(0,40)\n",
    "\n",
    "for(i in 1:40)\n",
    "{\n",
    "   # Your code here\n",
    "   \n",
    "   \n",
    "   \n",
    "   the.probability[i] = ? # Replace the question mark!\n",
    "}\n",
    "\n",
    "plot(N,the.probability)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 2 \n",
    "\n",
    "In this problem, we will use the sample generation skills from the previous problem to simulate dice rolls."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Part a)** \n",
    "\n",
    "Let $X$ be a random variable for the number rolled on a fair, six-sided die. Use the sample function (See Problem 1) to simulate $100$ values of $X$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Your code here\n",
    "numrolls = 100\n",
    "x = sample(1:6,numrolls,replace=TRUE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Run this cell to tabulate the counts for each outcome 1 through 6\n",
    "table(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Run this cell to get the proportions\n",
    "table(x)/numrolls"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Do you see what you expected to see? Run the previous three cells again with different values of \"numrolls\" to get more accurate results."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Part b)** \n",
    "\n",
    "Consider rolling <u>two</u> fair six-sided dice. What is the probability that the sum of the results is greater than or equal to 5? Work out the exact result by hand and then run a simulation to answer the question in the next cell. Compare your answers-- check your analytical solution and code until you can get them to match! "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Your code here\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "R",
   "language": "R",
   "name": "ir"
  },
  "language_info": {
   "codemirror_mode": "r",
   "file_extension": ".r",
   "mimetype": "text/x-r-source",
   "name": "R",
   "pygments_lexer": "r",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
